// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 21:44
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class LowestCommonAncestorT {
    List<List<TreeNode>> ans = new ArrayList<>();

    /**
     * 或得最小公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> travelP = new ArrayList<>();
        List<TreeNode> travelQ = new ArrayList<>();

        // 朴素遍历
        search(root, p, travelP);
        search(root, q, travelQ);
        return getCommon(travelP, travelQ);
    }

    /**
     * 获取最近相同节点
     *
     * @param travelP 访问p路径
     * @param travelQ 访问q路径
     * @return 返回相同节点
     */
    private TreeNode getCommon(List<TreeNode> travelP, List<TreeNode> travelQ) {
        if (travelP.isEmpty() || travelQ.isEmpty()) {
            return null;
        }
        TreeNode p = travelP.remove(0);
        TreeNode q = travelQ.remove(0);
        TreeNode next = getCommon(ans.get(0), ans.get(1));
        if (p.equals(q) && next == null) {
            // 判断相同实现时候，是从根节点开始，因为根节点是一定相同的，所以在保证后面没有节点相同的情况下，根节点是最近父节点
            return q;
        }
        return next;
    }


    /**
     * 遍历元素并遍历路径加入集合
     *
     * @param root 根节点
     * @param node
     * @param list
     */
    private void search(TreeNode root, TreeNode node, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        if (root.equals(node)) {
            ArrayList<TreeNode> tmp = new ArrayList<>();
            tmp.addAll(list);
            ans.add(tmp);
            return;
        }
        if (root.left != null) {
            search(root.left, node, list);
        }
        if (root.right != null) {
            search(root.right, node, list);
        }
        list.remove(root);
    }

    @Test
    public void shout() {
        Utils utils = new Utils();
        int[] nodes = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4};
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(lowestCommonAncestor(root, root.left, root.left.right.right));
    }

}
